1. Field of the Invention
The present invention generally relates to communication systems.
2. DESCRIPTION OF THE RELATED ART
A Log MAP (Maximum A Posteriori) processor processes information in accordance with the Log MAP algorithm. The Log MAP processor is usually part of a communication system that receives information which is to be decoded after such information has been exposed to noisy environments. The Log Map algorithm is a recursive algorithm for calculating the probability of a processing device being in a particular state at a given time based on received information. The probabilities are calculated by forward recursions and backward recursions over a defined time window or a block of information. The Log Map algorithm essentially is the recursive calculation of probabilities of being in certain states based on received information and the a priori probabilities of going to specific states from particular states. The states describe the condition of a process that generates the information that is ultimately received. The output of the Log MAP algorithm is called the LLR (Log Likelihood Ratio) which represents the probability that the original information (i.e., information prior to exposure to any noisy environment and prior to any processing) was a certain value. For example, for digital information, the LLR represents the probability that the original information was either a “0” bit or a “1” bit given all of the received data or observations. The Log MAP processor is a Soft Input Soft Output (SISO) device.
A SISO device receives soft information, processes such information in accordance with a particular algorithm or processing method and outputs soft information that can be used to make a hard decision about the received information or can be used for further processing. The soft information is probability data on the received information where such data give an indication of the confidence that is to be attributed to the value of the received information. For example, if received information was decoded to be a “0” bit, the soft information associated with that received information gives an indication of how likely that the original information was indeed a “0” bit. The SISO device also generates additional soft information as it is processing the input information; the difference between the additional generated soft information and the soft information at the input is called extrinsic information. In many applications where a SISO device is used, the extrinsic information is recursively inputted as soft input information to allow the SISO to generate more reliable soft information about a particular received information.
In processing digital information, a SISO device that employs the Log MAP algorithm (i.e., a Log MAP processor) processes the received information one bit at a time. The Log MAP algorithm and how the Log MAP processor operates are often represented by a trellis which has a certain number of states. Each state has a probability associated with it and transition probabilities indicating the likelihood of transitioning from one state to another state either forward or backward in time. Referring to FIG. 7, there is shown a portion of a trellis for a Log MAP processor; the trellis shows the possible transitions between states over time. Note that αtj, which is called a forward path metric, represents the probability of being in state j at time t for a forward recursion and βtj, which is called a backward path metric, also represents the probability of being in state j at time t given the received information. Also note that
      γ    t          i      ,      k        ,which is called a branch metric, is the probability of observing the received information given the transition from state i to state k and arriving at state k at time t. Although at most only two states are shown for each of the time instants, FIG. 7 can be, for example, an 8 state Radix-2 trellis where there are 8 states at each particular time instant representing the condition of the Log MAP processor. FIG. 7 is called a Radix-2 trellis because each state has two transition probabilities entering it and two transition probabilities leaving it. Thus, in general a radix-K trellis has K branches entering and K branches leaving each state in the trellis.
As communication systems have developed and as other systems that use Log MAP processors have developed, a need has emerged to process more information per unit time. For example, such communication systems or communication system components as turbo decoders or equalizers often use Log MAP processors as key components. In order to have communication systems with increased capacity and/or throughput, these key components have to process received information at relatively faster rates. Accordingly, there is a need to have Log MAP processors that can process information fast enough to meet the demands of the latest communication systems. In many applications, the Log MAP processing is implemented with the use of software. Generally, software implementations are inherently slower than hardware implementations of the Log MAP algorithm because of the time needed to execute software instructions within a processor or processing system. Indeed when the amount of processing per unit time is increasing, many times a software implemented algorithm becomes cannot be modified (i.e., reducing the number of instructions) sufficiently to meet the processing demand. In hardware implementations, the required hardware needed to increase the processing time often is complicated and costly because typically more components are added to perform the processing in parallel. What is therefore needed is a Log MAP processor that can process more information per unit of time than a Radix-2 Log MAP processor and avoids the limitations of software and hardware implementations.